package com.structure.algorithm;

/**
 * Created by sucre on 2015/11/29.
 */
public class SortedListToBinarySearchTree {
    private Node current;
    private int getListLength(Node head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }

    public BinaryTree sortedListToBST(Node head) {
        int size;
        current = head;
        size = getListLength(head);
        return sortedListToBSTHelper(size);
    }

    public BinaryTree sortedListToBSTHelper(int size) {
        if (size <= 0) {
            return null;
        }
        BinaryTree left = sortedListToBSTHelper(size / 2);
        BinaryTree root = new BinaryTree(Integer.valueOf(current.value));
        current = current.next;
        BinaryTree right = sortedListToBSTHelper(size - 1 - size / 2);
        root.leftNode = left;
        root.rightNode = right;
        return root;
    }
}
